package 递归;
/*
以编程角度来看，递归是指方法定义中调用方法本身的现象
把一个复杂问题层层转化为一个与原问题相似的规模较小的问题来求解
递归策略只需少量的程序就可描述出解题过程所需要的多层重复计算
递归要找到递归出口和递归原则
 */

public class DiGuiDemo {
    public static void main(String[] args) {
        //回顾不死神兔
        int[] arr=new int[20];

        arr[0]=1;
        arr[1]=1;
        for (int i=2;i< arr.length;i++){
            arr[i]=arr[i-1]+arr[i-2];
        }
        System.out.println(arr[19]);
        System.out.println(f(20));//StackOverflowError 当堆栈溢出时抛出的一个应用程序递归太深
    }

    //用递归解决，首先定义一个方法：
//    f(n)表示第n个月兔子对数
//    那么，第n-1个月的兔子对数如何表示:f(n-1)
//    第n-1个月的兔子对数如何表示:f(n-1)
//    第n-2个月的兔子对数如何表示:f(n-2)
    public static int f(int n) {
        if (n == 1 || n == 2) {//需要进行判断，当第三个月开始才是前两个月兔子对数之和不然会一直返回报错
        return  1;
        }else {
            return f(n - 1) + f(n - 2);//调用了f方法 一直返回
        }
    }
}
